{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Substring XOR Queries"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #hash-table #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #哈希表 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: substringXorQueries"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #子字符串异或查询"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个 <strong>二进制字符串</strong>&nbsp;<code>s</code>&nbsp;和一个整数数组&nbsp;<code>queries</code>&nbsp;，其中&nbsp;<code>queries[i] = [first<sub>i</sub>, second<sub>i</sub>]</code>&nbsp;。</p>\n",
    "\n",
    "<p>对于第&nbsp;<code>i</code>&nbsp;个查询，找到 <code>s</code>&nbsp;的 <strong>最短子字符串</strong>&nbsp;，它对应的 <strong>十进制</strong>值&nbsp;<code>val</code>&nbsp;与&nbsp;<code>first<sub>i</sub></code>&nbsp;<b>按位异或</b>&nbsp;得到&nbsp;<code>second<sub>i</sub></code>&nbsp;，换言之，<code>val ^ first<sub>i</sub> == second<sub>i</sub></code>&nbsp;。</p>\n",
    "\n",
    "<p>第&nbsp;<code>i</code>&nbsp;个查询的答案是子字符串&nbsp;<code>[left<sub>i</sub>, right<sub>i</sub>]</code> 的两个端点（下标从&nbsp;<strong>0</strong>&nbsp;开始），如果不存在这样的子字符串，则答案为&nbsp;<code>[-1, -1]</code>&nbsp;。如果有多个答案，请你选择&nbsp;<code>left<sub>i</sub></code>&nbsp;最小的一个。</p>\n",
    "\n",
    "<p>请你返回一个数组&nbsp;<code>ans</code>&nbsp;，其中&nbsp;<code>ans[i] = [left<sub>i</sub>, right<sub>i</sub>]</code>&nbsp;是第&nbsp;<code>i</code>&nbsp;个查询的答案。</p>\n",
    "\n",
    "<p><strong>子字符串</strong>&nbsp;是一个字符串中一段连续非空的字符序列。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>s = \"101101\", queries = [[0,5],[1,2]]\n",
    "<b>输出：</b>[[0,2],[2,3]]\n",
    "<b>解释：</b>第一个查询，端点为 <code>[0,2]</code> 的子字符串为 <strong>\"101\"</strong> ，对应十进制数字 <strong><code>5 ，且</code></strong> <strong><code>5 ^ 0 = 5</code></strong>&nbsp;，所以第一个查询的答案为 <code>[0,2]。第二个查询中，</code>端点为 <code>[2,3] 的子字符串为 </code><strong>\"11\" ，对应十进制数字</strong> <strong>3</strong>&nbsp;，且 <strong>3<code> ^ 1 = 2</code></strong><code>&nbsp;。所以第二个查询的答案为</code> <code>[2,3]</code> 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>s = \"0101\", queries = [[12,8]]\n",
    "<b>输出：</b>[[-1,-1]]\n",
    "<b>解释：</b>这个例子中，没有符合查询的答案，所以返回 <code>[-1,-1] 。</code>\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>s = \"1\", queries = [[4,5]]\n",
    "<b>输出：</b>[[0,0]]\n",
    "<b>解释：</b>这个例子中，端点为 <code>[0,0]</code> 的子字符串对应的十进制值为 <strong><code>1</code></strong><code>&nbsp;，且</code> <strong><code>1 ^ 4 = 5</code></strong><code>&nbsp;。所以答案为</code> <code>[0,0] 。</code>\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>s[i]</code>&nbsp;要么是&nbsp;<code>'0'</code>&nbsp;，要么是&nbsp;<code>'1'</code>&nbsp;。</li>\n",
    "\t<li><code>1 &lt;= queries.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= first<sub>i</sub>, second<sub>i</sub> &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [substring-xor-queries](https://leetcode.cn/problems/substring-xor-queries/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [substring-xor-queries](https://leetcode.cn/problems/substring-xor-queries/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"101101\"\\n[[0,5],[1,2]]', '\"0101\"\\n[[12,8]]', '\"1\"\\n[[4,5]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        n, m = len(s), {}\n",
    "\n",
    "        if (i := s.find('0')) >= 0:\n",
    "\n",
    "            m[0] = (i, i)  # 这样下面就可以直接跳过 '0' 了，效率更高\n",
    "\n",
    "        for l, c in enumerate(s):\n",
    "\n",
    "            if c == '0': continue\n",
    "\n",
    "            x = 0\n",
    "\n",
    "            for r in range(l, min(l + 30, n)):\n",
    "\n",
    "                x = (x << 1) | (ord(s[r]) & 1)\n",
    "\n",
    "                if x not in m:\n",
    "\n",
    "                    m[x] = (l, r)\n",
    "\n",
    "        NOT_FOUND = (-1, -1)\n",
    "\n",
    "        return [m.get(x ^ y, NOT_FOUND) for x, y in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(s)\n",
    "        m = {}\n",
    "        for i, x in enumerate(s):\n",
    "            if x=='0':\n",
    "                m[0]=(i ,i)\n",
    "                break\n",
    "        for l, c in enumerate(s):\n",
    "            if c=='0':\n",
    "                continue\n",
    "            x = 0\n",
    "            for r in range(l, min(l+30, n)):\n",
    "                x = (x<<1) | (ord(s[r]) & 1)\n",
    "                if x not in m:\n",
    "                    m[x] = (l ,r)\n",
    "        notFound = (-1, -1)\n",
    "        return [m.get(x^y, notFound) for x, y in queries]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:\n",
    "      n, m = len(s), {}\n",
    "      if (i := s.find('0')) >= 0:\n",
    "        m[0] = (i, i)\n",
    "      for l, x in enumerate(s):\n",
    "        if x == '0':\n",
    "          continue\n",
    "        num = 0\n",
    "        for r in range(l, min(l + 30, n)):\n",
    "          num = (num << 1) | (int(s[r]))\n",
    "          if num not in m:\n",
    "            m[num] = (l, r)\n",
    "      return [m.get(a ^ b, (-1, -1)) for a, b in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(s)\n",
    "        d = {}\n",
    "        for i in range(n):\n",
    "            x = 0\n",
    "            for j in range(i, min(i+30, n)):\n",
    "                x = (x << 1) | int(s[j])\n",
    "                if x not in d or j-i < d[x][1]-d[x][0]:\n",
    "                    d[x] = (i, j)\n",
    "        return [d.get(x ^ y, (-1, -1)) for x, y in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:\n",
    "        n, m = len(s), {}\n",
    "        if (i := s.find('0')) >= 0:\n",
    "            m[0] = (i, i)\n",
    "        for l, c in enumerate(s):\n",
    "            if c == '0': continue\n",
    "            x = 0\n",
    "            for r in range(l, min(l + 30, n)):\n",
    "                x = (x << 1) | (ord(s[r]) & 1)\n",
    "                if x not in m:\n",
    "                    m[x] = (l, r)\n",
    "        NOT_FOUND = (-1, -1)\n",
    "        return [m.get(x ^ y, NOT_FOUND) for x, y in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:\n",
    "        n, m = len(s), {}\n",
    "        if (i := s.find('0')) >= 0:\n",
    "            m[0] = (i, i)  # 这样下面就可以直接跳过 '0' 了，效率更高\n",
    "        for l, c in enumerate(s):\n",
    "            if c == '0': continue\n",
    "            x = 0\n",
    "            for r in range(l, min(l + 30, n)):\n",
    "                x = (x << 1) | (ord(s[r]) & 1)\n",
    "                if x not in m:\n",
    "                    m[x] = (l, r)\n",
    "        NOT_FOUND = (-1, -1)\n",
    "        return [m.get(x ^ y, NOT_FOUND) for x, y in queries]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:\n",
    "        n, m = len(s), {}\n",
    "        if (i := s.find('0')) >= 0:\n",
    "            m[0] = (i, i) # 这样下面就可以直接跳过'0'，效率更高\n",
    "        for l, c in enumerate(s):\n",
    "            if c == '0': continue\n",
    "            x = 0\n",
    "            for r in range(l, min(l + 30, n)):\n",
    "                x = (x << 1) | (ord(s[r]) & 1)\n",
    "                if x not in m:\n",
    "                    m[x] = (l, r)\n",
    "        NOT_FOUND = (-1, -1)\n",
    "        return [m.get(x ^ y, NOT_FOUND) for x, y in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:\n",
    "        n, m = len(s), {}\n",
    "\n",
    "        if (i := s.find('0')) >= 0:\n",
    "\n",
    "            m[0] = (i, i)  # 这样下面就可以直接跳过 '0' 了，效率更高\n",
    "\n",
    "        for l, c in enumerate(s):\n",
    "\n",
    "            if c == '0': continue\n",
    "\n",
    "            x = 0\n",
    "\n",
    "            for r in range(l, min(l + 30, n)):\n",
    "\n",
    "                x = (x << 1) | (ord(s[r]) & 1)\n",
    "\n",
    "                if x not in m:\n",
    "\n",
    "                    m[x] = (l, r)\n",
    "\n",
    "        NOT_FOUND = (-1, -1)\n",
    "\n",
    "        return [m.get(x ^ y, NOT_FOUND) for x, y in queries]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:\n",
    "        n, m = len(s), {}\n",
    "        if (i := s.find('0')) >= 0:\n",
    "            m[0] = (i, i)  # 这样下面就可以直接跳过 '0' 了，效率更高\n",
    "        for l, c in enumerate(s):\n",
    "            if c == '0': continue\n",
    "            x = 0\n",
    "            for r in range(l, min(l + 30, n)):\n",
    "                x = (x << 1) | (ord(s[r]) & 1)\n",
    "                if x not in m:\n",
    "                    m[x] = (l, r)\n",
    "        NOT_FOUND = (-1, -1)\n",
    "        return [m.get(x ^ y, NOT_FOUND) for x, y in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:\n",
    "        n, m = len(s), {}\n",
    "        if (i := s.find('0')) >= 0:\n",
    "            m[0] = (i, i)  # 这样下面就可以直接跳过 '0' 了，效率更高\n",
    "        for l, c in enumerate(s):\n",
    "            if c == '0': continue\n",
    "            x = 0\n",
    "            for r in range(l, min(l + 30, n)):\n",
    "                x = (x << 1) | (ord(s[r]) & 1)\n",
    "                if x not in m:\n",
    "                    m[x] = (l, r)\n",
    "        NOT_FOUND = (-1, -1)\n",
    "        return [m.get(x ^ y, NOT_FOUND) for x, y in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:\n",
    "        n, m = len(s), {}\n",
    "        if (i := s.find('0')) >= 0:\n",
    "            m[0] = (i, i)  # 这样下面就可以直接跳过 '0' 了，效率更高\n",
    "        for l, c in enumerate(s):\n",
    "            if c == '0': continue\n",
    "            x = 0\n",
    "            for r in range(l, min(l + 30, n)):\n",
    "                x = (x << 1) | (ord(s[r]) & 1)\n",
    "                if x not in m:\n",
    "                    m[x] = (l, r)\n",
    "        NOT_FOUND = (-1, -1)\n",
    "        return [m.get(x ^ y, NOT_FOUND) for x, y in queries]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:\n",
    "        n, m = len(s), {}\n",
    "        \n",
    "        # 如果字符串s中存在'0'，将其存储到哈希表中\n",
    "        if (i := s.find('0')) >= 0:\n",
    "            m[0] = (i, i)\n",
    "        \n",
    "        # 遍历s的所有子字符串，并将其存储到哈希表中\n",
    "        for l, c in enumerate(s):\n",
    "            if c == '0': continue\n",
    "            x = 0\n",
    "            for r in range(l, min(l + 30, n)):\n",
    "                x = (x << 1) | (ord(s[r]) & 1)\n",
    "                if x not in m:\n",
    "                    m[x] = (l, r)\n",
    "        \n",
    "        # 对于每一个查询，返回其答案\n",
    "        NOT_FOUND = (-1, -1)\n",
    "        return [m.get(x ^ y, NOT_FOUND) for x, y in queries]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:\n",
    "        n, m = len(s), {}\n",
    "        if (i := s.find('0')) >= 0:\n",
    "            m[0] = (i, i)  # 这样下面就可以直接跳过 '0' 了，效率更高\n",
    "        for l, c in enumerate(s):\n",
    "            if c == '0': continue\n",
    "            x = 0\n",
    "            for r in range(l, min(l + 30, n)):\n",
    "                x = (x << 1) | (ord(s[r]) & 1)\n",
    "                if x not in m:\n",
    "                    m[x] = (l, r)\n",
    "        NOT_FOUND = (-1, -1)\n",
    "        return [m.get(x ^ y, NOT_FOUND) for x, y in queries]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:\n",
    "        # n , m = len(s), {}\n",
    "        # if(i := s.find('0')) >= 0 : \n",
    "        #     m[0] = (i, i)\n",
    "        # for l, c in enumerate(s):\n",
    "        #     if c == '0':\n",
    "        #         continue\n",
    "        #     x = 0\n",
    "        #     for r in range(l , min(l + 30, n)):\n",
    "        #         x = (x << 1) | (ord(s[r]) & 1)\n",
    "        #         if x not in m:\n",
    "        #             m[x] = (l , r)\n",
    "        # NOT_FOUND = (-1, -1)\n",
    "        # return [m.get(x ^ y, NOT_FOUND) for x, y in queries]\n",
    "        n = len(s)\n",
    "        m = {}\n",
    "        for l in range(n):\n",
    "            x = 0\n",
    "            for r in range(l, min(l + 30, n)):\n",
    "                x = (x << 1) | (ord(s[r]) & 1)\n",
    "                if x not in m or r - l < (m[x][1] - m[x][0]):\n",
    "                    m[x] = (l, r)\n",
    "        NOT_FOUND = (-1, -1)\n",
    "        return [m.get(x ^ y, NOT_FOUND) for x, y in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:\n",
    "        n, m = len(s), {}\n",
    "        if (i := s.find('0')) >= 0:\n",
    "            m[0] = (i, i)  # 这样下面就可以直接跳过 '0' 了，效率更高\n",
    "        for l, c in enumerate(s):\n",
    "            if c == '0': continue\n",
    "            x = 0\n",
    "            for r in range(l, min(l + 30, n)):\n",
    "                x = (x << 1) | (ord(s[r]) & 1)\n",
    "                if x not in m:\n",
    "                    m[x] = (l, r)\n",
    "        NOT_FOUND = (-1, -1)\n",
    "        return [m.get(x ^ y, NOT_FOUND) for x, y in queries]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:\n",
    "        n, m = len(s), {}\n",
    "        if (i := s.find('0')) >= 0:\n",
    "            m[0] = [i, i]  # 这样下面就可以直接跳过 '0' 了，效率更高\n",
    "        for l, c in enumerate(s):\n",
    "            if c == '0': continue\n",
    "            x = 0\n",
    "            for r in range(l, min(l + 30, n)):\n",
    "                x = (x << 1) | (ord(s[r]) & 1)\n",
    "                if x not in m:\n",
    "                    m[x] = [l, r]\n",
    "        NOT_FOUND = [-1, -1]\n",
    "        return [m.get(x ^ y, NOT_FOUND) for x, y in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:\n",
    "        # lst_res = []\n",
    "        # for i in range(len(queries)):\n",
    "        #     num = str(bin(queries[i][0] ^ queries[i][1]))\n",
    "        #     num_bin = num[2:]\n",
    "        #     number = s.find(num_bin)\n",
    "        #     if number != -1:\n",
    "        #         lst_res.append([number, number+len(num_bin)-1])\n",
    "        #     else:\n",
    "        #         lst_res.append([-1, -1])\n",
    "        # return lst_res\n",
    "        m = {}\n",
    "        n = len(s)\n",
    "        for l in range(n):\n",
    "            x = 0\n",
    "            for r in range(l, min(l+30, n)):\n",
    "                x = (x << 1)|(ord(s[r]) & 1)\n",
    "                if x not in m or (r-l)<(m[x][1]-m[x][0]):\n",
    "                    m[x] = [l, r]\n",
    "        NOT_FOUND = [-1, -1]\n",
    "        return [m.get(x ^ y, NOT_FOUND) for x, y in queries] \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:\n",
    "        n, m = len(s), {}\n",
    "        if (i := s.find('0')) >= 0:\n",
    "            m[0] = (i, i)  # 这样下面就可以直接跳过 '0' 了，效率更高\n",
    "        for l, c in enumerate(s):\n",
    "            if c == '0': continue\n",
    "            x = 0\n",
    "            for r in range(l, min(l + 30, n)):\n",
    "                x = (x << 1) | (ord(s[r]) & 1)\n",
    "                if x not in m:\n",
    "                    m[x] = [l, r]\n",
    "        NOT_FOUND = [-1, -1]\n",
    "        return [m.get(x ^ y, NOT_FOUND) for x, y in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:\n",
    "        dic1, dic2 = {}, {}\n",
    "        for i in range(len(queries)):\n",
    "            queries[i] = queries[i][0] ^ queries[i][1]\n",
    "            dic1.setdefault(len(bin(queries[i])) - 2, set()).add(queries[i])\n",
    "        for i in range(1, min(len(s), max(dic1)) + 1):\n",
    "            if i in dic1:\n",
    "                pres = int(s[:i], 2)\n",
    "                if pres not in dic2:\n",
    "                    dic2[pres] = [0, i - 1]\n",
    "                for j in range(i, len(s)):\n",
    "                    pres = (pres << 1) % (1 << i) + int(s[j])\n",
    "                    if pres not in dic2:\n",
    "                        dic2[pres] = [j - i + 1, j]\n",
    "        return [dic2[x] if x in dic2 else [-1, -1] for x in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def substringXorQueries(\n",
    "        self, s: str, queries: List[List[int]]\n",
    "    ) -> List[List[int]]:\n",
    "        \"\"\"\n",
    "        val ^ first = second\n",
    "        val = first ^ second\n",
    "        将 val 转化为二进制字符串，将问题转化为子串查找问题（模式匹配）\n",
    "        \"\"\"\n",
    "        n = len(s)\n",
    "\n",
    "        res = []\n",
    "\n",
    "        for first, second in queries:\n",
    "            val = bin(first ^ second)[2:]\n",
    "            idx = s.find(val)\n",
    "            if idx == -1:\n",
    "                res.append([-1, -1])\n",
    "            else:\n",
    "                res.append([idx, idx + len(val) - 1])\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:\n",
    "        ans = []\n",
    "        for first, second in queries:\n",
    "            val = first ^ second\n",
    "            p = bin(val)[2:]\n",
    "            i = s.find(p)\n",
    "            if i >= 0:\n",
    "                ans.append([i, i+len(p)-1])\n",
    "            else:\n",
    "                ans.append([i, i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:\n",
    "        lst_res = []\n",
    "        for i in range(len(queries)):\n",
    "            num = str(bin(queries[i][0] ^ queries[i][1]))\n",
    "            num_bin = num[2:]\n",
    "            number = s.find(num_bin)\n",
    "            if number != -1:\n",
    "                lst_res.append([number, number+len(num_bin)-1])\n",
    "            else:\n",
    "                lst_res.append([-1, -1])\n",
    "        return lst_res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def substringXorQueries(self, s: str, queries: [[int]]) -> [[int]]:\n",
    "        ans=[]\n",
    "        for f1,s1 in queries:\n",
    "            res=f1^s1\n",
    "            s2=bin(res)[2::]\n",
    "            idx=s.find(s2)\n",
    "            if idx<0:\n",
    "                ans.append([-1,-1])\n",
    "            else:\n",
    "                ans.append([idx,idx+len(s2)-1])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:\n",
    "        n, m = len(s), len(queries)\n",
    "        ans = [[-1, -1] for _ in range(m)]\n",
    "        d = dict()\n",
    "        for i in range(m):\n",
    "            val = queries[i][0] ^ queries[i][1]\n",
    "            tmp = \"\"\n",
    "            size = 0\n",
    "            if not val:\n",
    "                tmp = \"0\"\n",
    "            else:\n",
    "                while val:\n",
    "                    tmp = str(val & 1) + tmp\n",
    "                    val >>= 1\n",
    "                    if val: size += 1\n",
    "            if tmp in d:\n",
    "                ans[i] = [d[tmp][0], d[tmp][1]]\n",
    "            else:\n",
    "                index = s.find(tmp)\n",
    "                if index != -1:\n",
    "                    ans[i] = [index, index + size]\n",
    "                    d[tmp] = (index, index + size)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:\n",
    "        ans = []\n",
    "        for fst, scd in queries:\n",
    "            x = fst ^ scd\n",
    "            s_x = bin(x)[2 : ]\n",
    "            i = s.find(s_x)\n",
    "            if i != -1:\n",
    "                ans.append([i, i + len(s_x) - 1])\n",
    "            else:\n",
    "                ans.append([-1, -1])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:\n",
    "        res = []\n",
    "        for i in queries:\n",
    "            target = i[1] ^ i[0]\n",
    "            target = bin(target)\n",
    "            l = s.find(target[2:])\n",
    "            r = l + len(target) - 3 if l != -1 else -1\n",
    "            res.append([l,r])\n",
    "        return res\n",
    "            \n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:\n",
    "        res = []\n",
    "        for l, r in queries:\n",
    "            obj = bin(l ^ r).removeprefix('0b')\n",
    "            pos = s.find(obj)\n",
    "            res.append([pos, -1 if pos == -1 else pos + len(obj) - 1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:\n",
    "        def kmpFind(s, pattern):\n",
    "            n = len(pattern)\n",
    "            dp = [[0,0] for _ in range(n)]\n",
    "            if(pattern[0] == '0'):\n",
    "                dp[0][0] = 1\n",
    "            else:\n",
    "                dp[0][1] = 1\n",
    "            x = 0\n",
    "            for i in range(1,n):\n",
    "                if(pattern[i] == '0'):\n",
    "                    dp[i][0] = i + 1\n",
    "                    dp[i][1] = dp[x][1]\n",
    "                else:\n",
    "                    dp[i][1] = i + 1\n",
    "                    dp[i][0] = dp[x][0]\n",
    "                x = dp[x][int(pattern[i])]\n",
    "\n",
    "            m = len(s)\n",
    "            j = 0\n",
    "            for i in range(m):\n",
    "                j = dp[j][int(s[i])]\n",
    "                if(j == n):\n",
    "                    return [i-n+1,i]\n",
    "            return [-1,-1]\n",
    "        def getDigit(num):\n",
    "            if(num == 0):\n",
    "                return '0'\n",
    "            res = ''\n",
    "            while(num > 0):\n",
    "                res = str(num%2) + res \n",
    "                num = num // 2\n",
    "            return res\n",
    "        result = []\n",
    "        for first, second in queries:\n",
    "            num = first^second\n",
    "            pattern = getDigit(num)\n",
    "            if(pattern in s):\n",
    "                result.append(kmpFind(s, pattern))\n",
    "            else:\n",
    "                result.append([-1,-1])\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:\n",
    "        def kmpFind(s, pattern):\n",
    "            n = len(pattern)\n",
    "            dp = [[0,0] for _ in range(n)]\n",
    "            if(pattern[0] == '0'):\n",
    "                dp[0][0] = 1\n",
    "            else:\n",
    "                dp[0][1] = 1\n",
    "            x = 0\n",
    "            for i in range(1,n):\n",
    "                if(pattern[i] == '0'):\n",
    "                    dp[i][0] = i + 1\n",
    "                    dp[i][1] = dp[x][1]\n",
    "                else:\n",
    "                    dp[i][1] = i + 1\n",
    "                    dp[i][0] = dp[x][0]\n",
    "                x = dp[x][int(pattern[i])]\n",
    "\n",
    "            m = len(s)\n",
    "            j = 0\n",
    "            for i in range(m):\n",
    "                j = dp[j][int(s[i])]\n",
    "                if(j == n):\n",
    "                    return [i-n+1,i]\n",
    "            return [-1,-1]\n",
    "        def getDigit(num):\n",
    "            if(num == 0):\n",
    "                return '0'\n",
    "            res = ''\n",
    "            while(num > 0):\n",
    "                res = str(num%2) + res \n",
    "                num = num // 2\n",
    "            return res\n",
    "        result = []\n",
    "        for first, second in queries:\n",
    "            num = first^second\n",
    "            pattern = getDigit(num)\n",
    "            if(pattern in s):\n",
    "                result.append(kmpFind(s, pattern))\n",
    "            else:\n",
    "                result.append([-1,-1])\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:\n",
    "        n, m = len(s), len(queries)\n",
    "        ans = [[-1, -1] for _ in range(m)]\n",
    "        d = dict()\n",
    "        for i in range(m):\n",
    "            val = queries[i][0] ^ queries[i][1]\n",
    "            if val in d:\n",
    "                ans[i] = d[val]\n",
    "            else:\n",
    "                tmp = \"\"\n",
    "                size = 0\n",
    "                num = val\n",
    "                if not val:\n",
    "                    tmp = \"0\"\n",
    "                else:\n",
    "                    while val:\n",
    "                        tmp = str(val & 1) + tmp\n",
    "                        val >>= 1\n",
    "                        if val: size += 1\n",
    "                index = s.find(tmp)\n",
    "                if index != -1:\n",
    "                    ans[i] = [index, index + size]\n",
    "                    d[num] = ans[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:\n",
    "        n, m = len(s), len(queries)\n",
    "        ans = [[-1, -1] for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            val = queries[i][0] ^ queries[i][1]\n",
    "            tmp = \"\"\n",
    "            size = 0\n",
    "            if not val:\n",
    "                tmp = \"0\"\n",
    "            else:\n",
    "                while val:\n",
    "                    tmp = str(val & 1) + tmp\n",
    "                    val >>= 1\n",
    "                    if val: size += 1\n",
    "            index = s.find(tmp)\n",
    "            if index != -1:\n",
    "                ans[i] = [index, index + size]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:\n",
    "        ans = []\n",
    "        for i in range(len(queries)):\n",
    "            str1 = bin(queries[i][0]^queries[i][1])[2:]\n",
    "            index = s.find(str1)\n",
    "            if index!=-1:\n",
    "                ans.append([index,index+len(str1)-1])\n",
    "            else:\n",
    "                ans.append([-1,-1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:\n",
    "        res = []\n",
    "        for a,b in queries:\n",
    "            c = bin(a^b)[2:]\n",
    "            if c in s:\n",
    "                idx =s.index(c)\n",
    "                res.append([idx, idx+len(c)-1])\n",
    "            else:\n",
    "                res.append([-1,-1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(s)\n",
    "        d = dict()\n",
    "    \n",
    "        for i in range(n):\n",
    "            if s[i] == '0':\n",
    "                if 0 not in d:\n",
    "                    d[0] = i\n",
    "                continue\n",
    "            now = 0\n",
    "            for j in range(31):\n",
    "                if i + j >= n:\n",
    "                    break\n",
    "                now = now * 2 + (s[i + j] == '1')\n",
    "                if now not in d:\n",
    "                    d[now] = i\n",
    "        ret = []\n",
    "        for a, b in queries:\n",
    "            a ^= b\n",
    "            p = d.get(a, -1)\n",
    "            if p == -1:\n",
    "                ret.append([-1, -1])\n",
    "            else:\n",
    "                ret.append([p, len(bin(a)) - 3 + p])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def num2(self, n):\n",
    "        s = ''\n",
    "        if n == 0:\n",
    "            return '0'\n",
    "        while n:\n",
    "            s += str(n & 1)\n",
    "            n = n >> 1\n",
    "        return s[::-1]\n",
    "    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            a = q[1] ^ q[0]\n",
    "            a = self.num2(a)\n",
    "            i = s.find(a)\n",
    "            if i == -1:\n",
    "                ans.append([-1,-1])\n",
    "            else:\n",
    "                ans.append([i, i+len(a)-1])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:\n",
    "        res = []\n",
    "        for item in queries:\n",
    "            cur_s = str(bin(item[0] ^ item[1]))[2:]\n",
    "            try:\n",
    "                cur_index = s.index(cur_s)\n",
    "                res.append([cur_index,cur_index+len(cur_s) -1])\n",
    "            except:\n",
    "                res.append([-1,-1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:\n",
    "        #暴力KMP\n",
    "        def kmpFind(s, pattern):\n",
    "            n = len(pattern)\n",
    "            dp = [[0,0] for _ in range(n)]\n",
    "            if(pattern[0] == '0'):\n",
    "                dp[0][0] = 1\n",
    "            else:\n",
    "                dp[0][1] = 1\n",
    "            x = 0\n",
    "            for i in range(1,n):\n",
    "                if(pattern[i] == '0'):\n",
    "                    dp[i][0] = i + 1\n",
    "                    dp[i][1] = dp[x][1]\n",
    "                else:\n",
    "                    dp[i][1] = i + 1\n",
    "                    dp[i][0] = dp[x][0]\n",
    "                x = dp[x][int(pattern[i])]\n",
    "\n",
    "            m = len(s)\n",
    "            j = 0\n",
    "            for i in range(m):\n",
    "                j = dp[j][int(s[i])]\n",
    "                if(j == n):\n",
    "                    return [i-n+1,i]\n",
    "            return [-1,-1]\n",
    "        def getDigit(num):\n",
    "            if(num == 0):\n",
    "                return '0'\n",
    "            res = ''\n",
    "            while(num > 0):\n",
    "                res = str(num%2) + res \n",
    "                num = num // 2\n",
    "            return res\n",
    "        result = []\n",
    "        for first, second in queries:\n",
    "            num = first^second\n",
    "            pattern = getDigit(num)\n",
    "            if(pattern in s):\n",
    "                result.append(kmpFind(s, pattern))\n",
    "            else:\n",
    "                result.append([-1,-1])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:\n",
    "        res_list = []\n",
    "        for i in queries:\n",
    "            first,second = i\n",
    "            b= str(bin(first^second)[2:])\n",
    "            left = s.find(b)\n",
    "            if left==-1:\n",
    "                right =-1\n",
    "            else:\n",
    "                right = left+len(b)-1\n",
    "            res_list.append([left,right])\n",
    "        return res_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(s)\n",
    "        c = Counter()\n",
    "        for i in range(30, 0, -1):\n",
    "            for j in range(n - i, -1, -1):\n",
    "                c[int(s[j: j + i], base=2)] = j\n",
    "        ans = []\n",
    "        for f, se in queries:\n",
    "            val = f ^ se\n",
    "            idx = c[val]\n",
    "            l = val.bit_length() if val else 1\n",
    "            if idx:\n",
    "                ans.append([idx, idx + l - 1])\n",
    "            else:\n",
    "                if int(s[: l], base=2) == val:\n",
    "                    ans.append([idx, l - 1])\n",
    "                else:\n",
    "                    ans.append([-1, -1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:\r\n",
    "        res = []\r\n",
    "        n = len(s)\r\n",
    "        # 预处理 s串 \r\n",
    "        mp = {}\r\n",
    "        for l in range(1, 32):\r\n",
    "            for st in range(n):\r\n",
    "                if st + l > n:\r\n",
    "                    break\r\n",
    "                num = int(s[st:st + l], 2)\r\n",
    "                if num not in mp:\r\n",
    "                    mp[num] = st \r\n",
    "\r\n",
    "        for x, y in queries:\r\n",
    "            # t ^ x = y \r\n",
    "            t = x ^ y \r\n",
    "            # 每个询问 kmp 查询也是不可接受的 \r\n",
    "            if t not in mp:\r\n",
    "                res.append([-1, -1])\r\n",
    "            else:\r\n",
    "                res.append([mp[t], mp[t] + t.bit_length() - 1 if t else mp[t]])\r\n",
    "        return res \r\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:\n",
    "        N = len(s)\n",
    "        MAX_BIT = 32\n",
    "        cache = dict()\n",
    "        for i, c in enumerate(s):\n",
    "            if s[i] == '1':\n",
    "                j, cur = 0, 0\n",
    "                while j < MAX_BIT and i + j < N:\n",
    "                    cur <<= 1\n",
    "                    cur |= (1 if s[i + j] == '1' else 0)\n",
    "                    if cur not in cache or j < cache[cur][1] - cache[cur][0]:\n",
    "                        cache[cur] = (i, i + j)\n",
    "                    j += 1\n",
    "            elif 0 not in cache:\n",
    "                cache[0] = (i, i)\n",
    "        ans = [cache[q[0] ^ q[1]] if q[0] ^ q[1] in cache else [-1, -1] for q in queries]\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:\n",
    "        N = len(s)\n",
    "        nums = dict()\n",
    "        x = s.find('0')\n",
    "        if x >= 0:\n",
    "            nums[0] = [x, x]\n",
    "        for i in range(N):\n",
    "            if s[i] == \"0\":\n",
    "                continue\n",
    "            n = 0\n",
    "            for j in range(i, min(i+30, N)):\n",
    "                n = (n<<1) | (ord(s[j]) - ord('0'))\n",
    "                if n not in nums:\n",
    "                    nums[n] = [i, j]\n",
    "        # print(nums)\n",
    "        return [nums.get(l^r, [-1, -1]) for l, r in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:\n",
    "        N = len(s)\n",
    "        nums = dict()\n",
    "        for i in range(N):\n",
    "            if s[i] == \"0\":\n",
    "                if 0 not in nums:\n",
    "                    nums[0] = [i,i]\n",
    "                continue\n",
    "            n = 0\n",
    "            for j in range(i, min(i+30, N)):\n",
    "                n = (n<<1) | (ord(s[j]) - ord('0'))\n",
    "                if n not in nums:\n",
    "                    nums[n] = [i, j]\n",
    "        # print(nums)\n",
    "        ans = []\n",
    "        for l, r in queries:\n",
    "            ans.append(nums.get(l^r, [-1, -1]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        n = len(s)\n",
    "        cnt = {}\n",
    "        for i in range(n):\n",
    "            cur = 0\n",
    "            for j in range(30):\n",
    "                if i + j >= n:\n",
    "                    break\n",
    "                cur = (cur << 1) + int(s[i + j])\n",
    "                if cur not in cnt or j + 1 < cnt[cur][1] - cnt[cur][0] + 1:\n",
    "                    cnt[cur] = [i, i + j]\n",
    "        \n",
    "        # print(cnt)\n",
    "        ans = []\n",
    "        for a, b in queries:\n",
    "            if a ^ b not in cnt:\n",
    "                ans.append([-1, -1])\n",
    "            else:\n",
    "                ans.append(cnt[a ^ b])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:\n",
    "                \n",
    "                ans = [];d = {}\n",
    "                n = len(s)\n",
    "                for l in range(n):\n",
    "                    x = 0\n",
    "                    for r in range(l,min(l+30,n)):\n",
    "                        x = (x << 1) | (int(s[r]))\n",
    "                        if x not in d or r - l < d[x][1] - d[x][0]:\n",
    "                            d[x] = [l,r]\n",
    "                        \n",
    "                for first,second in queries:\n",
    "                    num = first ^ second\n",
    "                    ans.append(d[num] if d.get(num) else [-1,-1])\n",
    "                return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(s)\n",
    "        d = {}\n",
    "        for l in range(n):\n",
    "            if s[l] == '0':\n",
    "                if not 0 in d:\n",
    "                    d[0] = [l, l]\n",
    "            else:\n",
    "                # 最长枚举长度为30\n",
    "                x = 0\n",
    "                for r in range(l, min(n, l + 30)):\n",
    "                    x = (x << 1) | (int(s[r]))\n",
    "                    if not x in d:\n",
    "                        d[x] = [l, r]\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            c = q[0] ^ q[1]\n",
    "            if not c in d:\n",
    "                ans.append([-1, -1])\n",
    "            else:\n",
    "                ans.append(d[c])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(s)\n",
    "        m = {}\n",
    "        i = s.find('0')\n",
    "        if i >= 0 : m[0] = [i, i]\n",
    "        for l, c in enumerate(s):\n",
    "            if c == '0': continue\n",
    "            # x = 0\n",
    "            for r in range(l, min(l + 30, n)):\n",
    "                x = int(s[l: r+1], 2)\n",
    "                if x not in m:\n",
    "                    m[x] = [l, r]\n",
    "        ans = []\n",
    "        for a, b in queries:\n",
    "            val = a ^ b\n",
    "            ans.append(m.get(val, [-1, -1]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:\n",
    "        dic = {}\n",
    "        n = len(s)\n",
    "        res = []\n",
    "        def getnum(strs):\n",
    "            n = len(strs)\n",
    "            cnt = n - 1\n",
    "            arr = 0\n",
    "            for i in range(n):\n",
    "                if strs[i] == '0':\n",
    "                    cnt -= 1\n",
    "                    continue\n",
    "                arr += int(strs[i]) * 2 ** cnt\n",
    "                cnt -= 1\n",
    "            return arr\n",
    "\n",
    "        for i in range(n):\n",
    "            if s[i] == '0':\n",
    "                dic[0] = [i, i]\n",
    "                break\n",
    "        for i in range(n):\n",
    "            x = 0\n",
    "            if s[i] == '0':\n",
    "                continue\n",
    "            for j in range(i, min(i + 30, n)):\n",
    "                x = getnum(s[i:j + 1])\n",
    "                if x not in dic:\n",
    "                    dic[x] = [i, j]\n",
    "        for q in queries:\n",
    "            res.append(dic.get(q[0] ^ q[1], [-1, -1]))\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:\n",
    "        # 2^30 >= 10^9\n",
    "        n = len(s)\n",
    "        mp = {}\n",
    "        if (i := s.find('0')) >= 0:\n",
    "            mp[0] = [i, i]\n",
    "        for l, x in enumerate(s):\n",
    "            if x == '0': # 去掉前导0\n",
    "                continue\n",
    "            y = 0\n",
    "            for r in range(l, min(l + 30, n)):\n",
    "                y = (y << 1) | (int(s[r]))\n",
    "                if y not in mp:\n",
    "                    mp[y] = [l, r]\n",
    "        return [mp.get(a ^ b,[-1, -1]) for a, b in queries]\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        n = len(s)\n",
    "        cnt = {}\n",
    "        idx = s.find('0')\n",
    "        cnt[0] = [idx, idx]\n",
    "        for i in range(n):\n",
    "            if i == '0':\n",
    "                continue\n",
    "            cur = 0\n",
    "            for j in range(30):\n",
    "                if i + j >= n:\n",
    "                    break\n",
    "                cur = (cur << 1) + int(s[i + j])\n",
    "                if cur not in cnt or j + 1 < cnt[cur][1] - cnt[cur][0] + 1:\n",
    "                    cnt[cur] = [i, i + j]\n",
    "        \n",
    "        # print(cnt)\n",
    "        ans = []\n",
    "        for a, b in queries:\n",
    "            if a ^ b not in cnt:\n",
    "                ans.append([-1, -1])\n",
    "            else:\n",
    "                ans.append(cnt[a ^ b])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(s)\n",
    "        d = {}\n",
    "        zero = None\n",
    "        for left in range(n):\n",
    "            if s[left] == '0':\n",
    "                if zero == None:\n",
    "                    zero = left\n",
    "                continue\n",
    "            ans = 0\n",
    "            for right in range(left, min(left + 30, n)):\n",
    "                ans = (ans << 1) | int(s[right])\n",
    "                if ans not in d:\n",
    "                    d[ans] = [left, right]\n",
    "        res = []\n",
    "        for i in range(len(queries)):\n",
    "            temp = queries[i][0] ^ queries[i][1]\n",
    "            if temp in d:\n",
    "                res.append(d[temp])\n",
    "            elif temp == 0 and zero != None:\n",
    "                res.append([zero, zero])\n",
    "            else:\n",
    "                res.append([-1, -1])\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def substringXorQueries(self, s: str, q: List[List[int]]) -> List[List[int]]:\n",
    "        n=len(s)\n",
    "        h={}\n",
    "        for i in range(n):\n",
    "            if s[i]=='0':\n",
    "                if 0 not in h:\n",
    "                    h[0]=[i,i]\n",
    "                continue\n",
    "            for j in range(1,32):\n",
    "                t=int(s[i:i+j],2)\n",
    "                if t not in h:\n",
    "                    h[t]=[i,i+j-1]\n",
    "        # print(h)\n",
    "        ans=[]\n",
    "        for i,j in q:\n",
    "            k=i^j\n",
    "            if k not in h:\n",
    "                ans.append([-1,-1])\n",
    "            else:\n",
    "                ans.append(h[k])\n",
    "            # print(i,j,k,ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def substringXorQueries(self, s: str, q: List[List[int]]) -> List[List[int]]:\n",
    "        h={}\n",
    "        p0=s.find('0')\n",
    "        if p0!=-1:\n",
    "            h[0]=[p0,p0]\n",
    "        n=len(s)\n",
    "        for i in range(n):\n",
    "            if s[i]=='0':\n",
    "                continue\n",
    "            for j in range(1,32):\n",
    "                k=int(s[i:i+j],2)\n",
    "                if k not in h:\n",
    "                    h[k]=[i,i+j-1]\n",
    "        ans=[]\n",
    "        for i,j in q:\n",
    "            i^=j\n",
    "            if i not in h:\n",
    "                ans.append([-1,-1])\n",
    "            else:\n",
    "                ans.append(h[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(s)\n",
    "        p = dict()\n",
    "        for i in range(n):\n",
    "            t = 0\n",
    "            if int(s[i]) == 0:\n",
    "                if int(s[i]) not in p:\n",
    "                    p[int(s[i])] = [i,i]\n",
    "                continue\n",
    "            for j in range(31):\n",
    "                if i+j >= n:\n",
    "                    break\n",
    "                t = (t << 1) | int(s[i+j])\n",
    "                if t not in p:\n",
    "                    p[t] = [i, i+j]\n",
    "                    #print(t, p[t])\n",
    "        ans = []\n",
    "        for x, y in queries:\n",
    "            if x ^ y in p:\n",
    "                ans.append(p[x^y])\n",
    "            else:\n",
    "                ans.append([-1,-1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:\n",
    "        resMap = {}\n",
    "        n = len(s)\n",
    "        for start in range(n):\n",
    "            if s[start] == '0':\n",
    "                if 0 not in resMap:\n",
    "                    resMap[0] = [start, start]\n",
    "                continue\n",
    "                \n",
    "            v = 0\n",
    "            for j in range(start, min(start+32, n)):\n",
    "                v = (v<<1) + int(s[j])\n",
    "                if v not in resMap:\n",
    "                    resMap[v] = [start, j]\n",
    "        \n",
    "        res = []\n",
    "        for q in queries:\n",
    "            v = q[0]^q[1]\n",
    "            if v in resMap:\n",
    "                res.append(resMap[v])\n",
    "            else:\n",
    "                res.append([-1, -1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:\n",
    "        vis = collections.defaultdict(dict)\n",
    "        for i, c in enumerate(s):\n",
    "            if c in vis[1]:\n",
    "                continue\n",
    "            vis[1][c] = [i, i]\n",
    "            if len(vis[1]) == 2:\n",
    "                break\n",
    "\n",
    "        ans = []\n",
    "        for fst, snd in queries:\n",
    "            val = fst ^ snd\n",
    "            bval = bin(val)[2:]\n",
    "            length = len(bval)\n",
    "            if length not in vis:\n",
    "                for i in range(len(s)-length+1):\n",
    "                    if s[i] == '0' or s[i:i+length] in vis[length]:\n",
    "                        continue\n",
    "                    vis[length][s[i:i+length]] = [i, i+length-1]\n",
    "            ans.append(vis[length].get(bval, [-1,-1]))\n",
    "\n",
    "        return ans\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:\n",
    "        ans = []\n",
    "        nums_dict = dict()\n",
    "        for i in range(len(queries)):\n",
    "            str1 = bin(queries[i][0]^queries[i][1])[2:]\n",
    "            if str1 in nums_dict:\n",
    "                ans.append(nums_dict[str1])\n",
    "            else:\n",
    "                index = s.find(str1)\n",
    "                if index!=-1:\n",
    "                    ans.append([index,index+len(str1)-1])\n",
    "                    nums_dict[str1] = [index,index+len(str1)-1]\n",
    "                else:\n",
    "                    ans.append([-1,-1])\n",
    "                    nums_dict[str1] = [-1,-1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:\n",
    "        q = [x^y for x, y in queries]\n",
    "        n = len(s)\n",
    "        d = dict()\n",
    "        for i in range(n):\n",
    "            if s[i] == \"1\":\n",
    "                tmp = 0\n",
    "                for j in range(i, min(i + 32, n)):\n",
    "                    tmp = 2 * tmp + int(s[j])\n",
    "                    if tmp not in d:\n",
    "                        d[tmp] = [i, j]\n",
    "            else:\n",
    "                if 0 not in d:\n",
    "                    d[0] = [i, i]\n",
    "                    \n",
    "        ans = list()\n",
    "        # print(q)\n",
    "        for qi in q:\n",
    "            if qi in d:\n",
    "                ans.append(d[qi])\n",
    "            else:\n",
    "                ans.append([-1, -1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        # 00001\n",
    "        # 100000001\n",
    "\n",
    "        q = []\n",
    "        for ff, ss in queries:\n",
    "            q.append(ff ^ ss)\n",
    "\n",
    "        # {5: []}\n",
    "\n",
    "        res = []\n",
    "\n",
    "        def sw(size, mp):\n",
    "            left = 0\n",
    "            right = left + size\n",
    "\n",
    "            while right <= len(s):\n",
    "                val = int('0b' + s[left:right], base = 2)\n",
    "                if val not in mp:\n",
    "                    mp[val] = [left, right - 1]\n",
    "                left += 1\n",
    "                right += 1\n",
    "\n",
    "\n",
    "\n",
    "        mm = {}\n",
    "        for i in range(1, 31):\n",
    "            sw(i, mm)\n",
    "        \n",
    "        res = []\n",
    "\n",
    "        for qq in q:\n",
    "            res.append(mm.get(qq, [-1, -1]))\n",
    "        \n",
    "        return res\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        # 00001\n",
    "        # 100000001\n",
    "\n",
    "        q = []\n",
    "        for ff, ss in queries:\n",
    "            q.append(ff ^ ss)\n",
    "\n",
    "        # {5: []}\n",
    "\n",
    "        res = []\n",
    "\n",
    "        def sw(size, mp):\n",
    "            left = 0\n",
    "            right = left + size\n",
    "            val = int('0b' + s[left:right], base = 2)\n",
    "            if val not in mp:\n",
    "                mp[val] = [left, right - 1]\n",
    "\n",
    "            po = pow(2, size - 1)\n",
    "            left += 1\n",
    "            right += 1\n",
    "\n",
    "            while right <= len(s):\n",
    "                # val = int('0b' + s[left:right], base = 2)\n",
    "                val = (val - po * int(s[left - 1])) * 2 + int(s[right - 1])\n",
    "                if val not in mp:\n",
    "                    mp[val] = [left, right - 1]\n",
    "                left += 1\n",
    "                right += 1\n",
    "\n",
    "\n",
    "\n",
    "        mm = {}\n",
    "        for i in range(1, 31):\n",
    "            sw(i, mm)\n",
    "        \n",
    "        res = []\n",
    "\n",
    "        for qq in q:\n",
    "            res.append(mm.get(qq, [-1, -1]))\n",
    "        \n",
    "        return res\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:\n",
    "        qd=collections.defaultdict(list)\n",
    "        lm=Counter()\n",
    "        firstzero=-1\n",
    "        for i,query in enumerate(queries):\n",
    "            l,r=query\n",
    "            bins=bin(r^l)[2:]\n",
    "           # print(bins)\n",
    "            qd[bins].append(i)\n",
    "            lm[len(bins)]+=1\n",
    "        ql=len(queries)\n",
    "        ans=[[-1,-1] for _ in range(ql)]\n",
    "        n=len(s)\n",
    "       # print(qd)\n",
    "        for i in range(n):\n",
    "            if s[i]=='0' and firstzero==-1 and '0' in qd:\n",
    "                firstzero=i\n",
    "                for i0 in qd['0']:\n",
    "                    ans[i0]=[i,i]\n",
    "                if lm[1]==1:\n",
    "                    del lm[1]\n",
    "                else:\n",
    "                    lm[1]-=1\n",
    "            if s[i]=='1':\n",
    "                delq=[]\n",
    "                for lgth in lm.keys():\n",
    "                    if n-1-i+1<lgth:\n",
    "                        continue\n",
    "                    curr=s[i:i+lgth] \n",
    "                   # print('lm',lm)\n",
    "                    if curr in qd:\n",
    "                        for qdv in qd[curr]:\n",
    "                           # print(curr,i,lgth)\n",
    "                            ans[qdv]=[i,i+lgth-1]\n",
    "                        del qd[curr]\n",
    "                        lm[lgth]-=1\n",
    "                        if lm[lgth]==0:\n",
    "                            delq.append(lgth)\n",
    "                for lgth in delq:\n",
    "                    del lm[lgth]\n",
    "        return ans\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def substringXorQueries(\n",
    "        self, s: str, queries: List[List[int]]\n",
    "    ) -> List[List[int]]:\n",
    "        \"\"\"\n",
    "        val ^ first = second\n",
    "        val = first ^ second\n",
    "        \n",
    "        0 <= first, second <= 10^9\n",
    "        0 <= first ^ second <= 10^9\n",
    "        即 0 <= val <= 10^9 < 2^30\n",
    "        val 对应的二进制字符串长度最多 30\n",
    "\n",
    "        我们可以预处理字符串 s 所有长度小于等于 30 的子串\n",
    "        \"\"\"\n",
    "        n = len(s)\n",
    "\n",
    "        val2idx = defaultdict(lambda: [-1, -1])\n",
    "\n",
    "        idx0, idx1 = s.find('0'), s.find('1')\n",
    "        if idx0 != -1:\n",
    "            val2idx[0] = [idx0, idx0]\n",
    "        if idx1 != -1:\n",
    "            val2idx[1] = [idx1, idx1]\n",
    "\n",
    "        for k in range(2, 31):\n",
    "            for i in range(0, n - k + 1):\n",
    "                if s[i] == '0':\n",
    "                    continue\n",
    "\n",
    "                val = int(s[i: i + k], 2)\n",
    "                if val not in val2idx:\n",
    "                    val2idx[val] = [i, i + k - 1]\n",
    "\n",
    "        res = []\n",
    "\n",
    "        for first, second in queries:\n",
    "            res.append(val2idx[first ^ second])\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def substringXorQueries(\n",
    "        self, s: str, queries: List[List[int]]\n",
    "    ) -> List[List[int]]:\n",
    "        \"\"\"\n",
    "        val ^ first = second\n",
    "        val = first ^ second\n",
    "        \n",
    "        因为 0 <= first, second <= 10^9\n",
    "        所以 0 <= first ^ second <= 10^9\n",
    "        即 0 <= val <= 10^9 < 2^30\n",
    "        因此，val 对应的二进制字符串长度不超过 30\n",
    "\n",
    "        我们可以预处理字符串 s 所有长度小于等于 30 的子串对应的索引位置\n",
    "\n",
    "        \"\"\"\n",
    "        n = len(s)\n",
    "\n",
    "        val2idx = defaultdict(lambda: [-1, -1])\n",
    "\n",
    "        idx0, idx1 = s.find('0'), s.find('1')\n",
    "        if idx0 != -1:\n",
    "            val2idx[0] = [idx0, idx0]\n",
    "        if idx1 != -1:\n",
    "            val2idx[1] = [idx1, idx1]\n",
    "\n",
    "        idx2, idx3 = s.find('10'), s.find('11')\n",
    "        if idx2 != -1:\n",
    "            val2idx[2] = [idx2, idx2 + 1]\n",
    "        if idx3 != -1:\n",
    "            val2idx[3] = [idx3, idx3 + 1]\n",
    "\n",
    "        for k in range(3, 31):\n",
    "            for i in range(0, n - k + 1):\n",
    "                if s[i] == '0':\n",
    "                    continue\n",
    "\n",
    "                val = int(s[i: i + k], 2)\n",
    "                if val not in val2idx:\n",
    "                    val2idx[val] = [i, i + k - 1]\n",
    "\n",
    "        res = []\n",
    "\n",
    "        for first, second in queries:\n",
    "            res.append(val2idx[first ^ second])\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:\n",
    "  \n",
    "        m = len(queries)\n",
    " \n",
    "        dct = defaultdict(lambda: inf)\n",
    "        res = defaultdict(lambda: [-1, -1])\n",
    "            \n",
    "        n = len(s)\n",
    "        for i in range(n):\n",
    "            pre = 0\n",
    "            for j in range(i, n):\n",
    "                pre = pre*2 + int(s[j])\n",
    "                if j-i+1>32:\n",
    "                    break\n",
    "                cur = j-i+1\n",
    "                if cur < dct[pre]:\n",
    "                    dct[pre] = cur\n",
    "                    res[pre] = [i, j]\n",
    "        return [res[a^b] for a, b in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:\n",
    "                \n",
    "                ans = [];d = defaultdict(list)\n",
    "                n = len(s)\n",
    "                for l in range(n):\n",
    "                    x = 0\n",
    "                    for r in range(l,min(l+30,n)):\n",
    "                        x = (x << 1) | (int(s[r]))\n",
    "                        if not d[x] or r - l < d[x][1] - d[x][0]:\n",
    "                            d[x] = [l,r]\n",
    "                        \n",
    "                for first,second in queries:\n",
    "                    num = first ^ second\n",
    "                    ans.append(d[num] if d[num] else [-1,-1])\n",
    "                return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:\n",
    "                \n",
    "                ans = [];d = defaultdict(list)\n",
    "                for i in range(len(s)):\n",
    "                    if s[i] == '0':\n",
    "                        if not d[0]:d[0] = [i,i]\n",
    "                    else:\n",
    "                        if not d[1]:d[1] = [i,i]\n",
    "                    if d[0] and d[1]:\n",
    "                        break\n",
    "                for Len in range(2,31):\n",
    "                    l = 0;num = 0\n",
    "                    for r in range(len(s)):\n",
    "                        num = num << 1 | int(s[r])\n",
    "                        if r - l + 1 == Len:\n",
    "                            \n",
    "                            if not d[num]:\n",
    "                                d[num] = [l,r]\n",
    "                            if s[l] == '1':\n",
    "                                num ^= (1<<(Len-1))\n",
    "                            l += 1\n",
    "                        \n",
    "                        \n",
    "                for first,second in queries:\n",
    "                    num = first ^ second\n",
    "                    ans.append(d[num] if d[num] else [-1,-1])\n",
    "                return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:\n",
    "                \n",
    "                ans = [];d = defaultdict(list)\n",
    "                for i in range(len(s)):\n",
    "                    if s[i] == '0':\n",
    "                        if not d[0]:d[0] = [i,i]\n",
    "                    else:\n",
    "                        if not d[1]:d[1] = [i,i]\n",
    "                    if d[0] and d[1]:\n",
    "                        break\n",
    "                for Len in range(2,31):\n",
    "                    l = 0;num = 0\n",
    "                    for r in range(len(s)):\n",
    "                        num = num << 1 | int(s[r])\n",
    "                        if r - l + 1 == Len:\n",
    "                            \n",
    "                            if not d[num]:\n",
    "                                d[num] = [l,r]\n",
    "                            if s[l] == '1':\n",
    "                                num ^= (1<<(Len-1))\n",
    "                            l += 1\n",
    "                        \n",
    "                        \n",
    "                for first,second in queries:\n",
    "                    num = first ^ second\n",
    "                    ans.append(d[num] if d[num] else [-1,-1])\n",
    "                return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
